# -*- coding: utf-8 -*-

"""剑指 Offer II 084. 含有重复元素集合的全排列 
给定一个可包含重复数字的整数集合 nums ，按任意顺序 返回它所有不重复的全排列。

示例 1：
输入：nums = [1,1,2]
输出：
[[1,1,2],
 [1,2,1],
 [2,1,1]]

示例 2：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

提示：
1 <= nums.length <= 8
-10 <= nums[i] <= 10"""

from collections import Counter

class Solution:
    """在经典的排列问题基础上，将结果去重，还是回溯+递归；
    如果剪枝，可见例1中，两个位置都是1，同一次选择中占用2次机会，所以有重复，此时可以考虑用哈希字典 Counter 将集合初始化
    
    停止条件：
    Counter为空，元素消耗完"""
    def permuteUnique(self, nums):
        answer, counter = [], Counter(nums)
        def fork(counter, perm):
            if not counter:
                answer.append(perm)
                return

            for n in counter.keys():
                counter_new = counter.copy()
                perm_new = perm.copy()
                perm_new.append(n)
                if counter_new[n] > 1:
                    counter_new[n] -= 1
                else:
                    del counter_new[n]
                fork(counter_new, perm_new)
        
        fork(counter, [])
        return answer


if __name__ == '__main__':
    so = Solution()
    print(so.permuteUnique([1,1,2]))
    print(so.permuteUnique([1,2,3]))
